#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        self.threshold = threshold
        self.rows = rows
        self.cols = cols

        self.visited = [ [ 0 for i in range(cols) ] for j in range(rows)]
        self.count = 0

        self.rec_find(0, 0)

        return self.count

    def digit_sum(self, num):
        s = 0

        while num != 0:
            s += num % 10
            num //= 10

        return s

    def valid(self, row, col):
        return self.digit_sum(row) + self.digit_sum(col) <= self.threshold

    def rec_find(self, row, col):
        # 一定要把范围判断放在前面, 不然先查看visited, 可能会index out of range!
        # 任何时候, 都把数组索引判定放在最前面!
        if row == self.rows or col == self.cols:
            return

        if self.visited[row][col] == 1:
            return

        self.visited[row][col] = 1      # 无论是否valid, 都标记访问过
        if not self.valid(row, col):
            # 如果row, col 这个节点非法, 机器人不能到达.
            # 也自然不能通过这个节点到达此节点的相邻节点.
            # 所以不用再尝试相邻节点, 直接返回.
            return

        self.count += 1

        # 尝试此节点的相邻节点.
        self.rec_find(row, col+1)
        self.rec_find(row+1, col)


def test():
    s = Solution()
    # ret = s.movingCount(8, 10, 10)
    ret = s.movingCount(15, 20, 20)
    print(ret)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
